The present invention relates to methods for achieving a position code, a method for decoding of a position code, a computer program for these purposes, a product that is provided with a position code and devices for position coding and for decoding of a position code.
The use of position codes on a surface as a tool for recording in electronic form information that is written or drawn on the surface is already known.
In U.S. Pat. No. 5,477,012 a pen is described that detects optically a position code consisting of various symbols on a surface. The pen decodes the position code and gene-rates pairs of coordinates that describe the movement of the pen across the surface. Each position is coded by a specific symbol. If the position code is to code many positions, this results in the disadvantage that the symbols become complex and hence difficult to detect correctly. On the other hand, if the symbols are made larger, the resolution is decreased.
In WO 92/17859 a position code is described in which each position is coded by means of a plurality of symbols and each symbol contributes to the coding of more than one position. Adjacent positions are thus coded by partially shared symbols.
In Appendix A of WO 92/17859 the following example is given of how the position code can be built up and how a position can be decoded.
Start from the following m-sequences: s=(0,0,1,0,1,1,1) and t=(0,1,1). Build up a position-coding pattern by letting a first column in the pattern be the same as the sequence s. In order to build up the following columns, look at the t-sequence. If the first element in the t-sequence is 0, then the second column consists of the s-sequence. If the first element is 1 instead, then the second column consists of the s-sequence with a circular shift of one step. Subsequent columns are built up in a corresponding way in accordance with the values of the elements in the t-sequence. The following pattern is thus obtained:
Now assume that we want to find the position of a partial surface with the following subset of the pattern.
The first column in the subset is (1,0,1). This sub-sequence appears in position 2 in the s-sequence. The circular shifts in the subset are (1,1). This sub-sequence appears in position 1 in the t-sequence. The accumulated shifts in the pattern are (0,0,1,2) and therefore the vertical position of the subset is 2+0=2. The position of the subset on the partial surface is thus (1,2).
This pattern has the advantage that it can be coded on a base using simple symbols, for example a first symbol for a zero and a second symbol for a one.
An interesting property of a position-coding pattern of this type is, however, the ability to code a large pattern with many unique positions so that position determination can be carried out on as large a surface as possible. In the example above, the size in the vertical direction is limited by the length of the s-sequence and the size in the horizontal direction by the length of the t-sequence. The length of these sequences cannot be increased without limit as the sequences must have the property that if a sub-sequence is taken of k bits, then this sub-sequence must only occur in one single place in the sequence. An increase in the length of the sequence can thus bring about an increase in the length of the sub-sequence and thereby an increase in the partial surface that needs to be recorded in order to be able to determine a position.
In WO 01/26032, WO 01/26033 and WO 01/26034, which have been assigned to the Applicant of the present application, another position-coding pattern is described that is based on the same basic principles as those in WO 92/17859, but which enables coding of a larger number of positions.
In one embodiment of this pattern, a first number sequence is used that has the property that the place in the number sequence of each sub-sequence or partial sequence of a predetermined length is unambiguously determined and this number sequence is printed out in columns over the surface with various rotations or circular shifts. Instead of using a binary second sequence (the t-sequence in WO 92/17859), however, larger circular shifts between adjacent columns are permitted.
The surface is further divided into code windows. Each code window comprises at least three columns with number sequences and overlaps the adjacent code windows by one number sequence. Using the shifts between adjacent columns, the position of the code window along the x-axis is coded. The shifts between the number sequences in a code window thus define a position, the first code window having the position 0, the next 1, and so on.
When reading off the position code, the reading device will often, however, record parts of two code windows. In order that the position of the code windows relative to the read-off image of the position code can be determined, shifts in a first range are used to indicate the least significant shift for the position and shifts in a second range for other shifts in the position.
The coding of a y-coordinate is carried out in a corresponding way.
This position code has been found to work very well and permits coding of a very large number of positions. There is, however, a desire to improve the error-correction properties of the position code.
Assume, for example, that the least subset that unambiguously codes a position in the x-direction comprises five shifts. From these five shifts, a position of a code window can be determined. The positions of two adjacent code windows thus usually only differ in the last digit (the last shift). For three consecutive code windows the shifts can, for example, be as follows:
25,15,34,18,3; 25,15,34,18,4; 25,15,34,18,5;
A common method of detecting errors is based on reading off more information than what is needed for the task concerned. With the above-mentioned coding, it is difficult to read off extra information which is suitable for use for error detection. Assume, for example, that a reading device records the two last shifts from the first of the above three code windows, and the first three shifts from the following code window, that is 18,3,25,15,34. Assume further that an error occurs that means that 18,4,25,15,34 is recorded. The reading off of, for example, two more shifts, one on each side of the five, provides no extra information that makes it possible to detect the error.
If, when coding in the x-direction, a number sequence is used with the property that each partial sequence (sub-sequence) of a predetermined length has an unambiguously determined place in the number sequence, error correction is facilitated. On the other hand, the practical problem arises that this number sequence must have a large base, that is must permit large shifts, if it is to be possible to code many positions. A very large table is then required in order to find the place in the number sequence to which a read-off partial sequence corresponds, which in turn requires a large amount of memory. It is, however, desirable for the decoding to be able to be carried out in, for example, a hand-held reading device with limited memory and processor capacity. It is also desirable that the coding should be able to be carried out in devices with limited memory and processor capacity.
An object of the present invention is therefore to reduce the above-mentioned problems by providing a position code that makes it possible to code a very large number of positions, that permits error correction, but yet does not require the storage of large tables for the coding and decoding and which therefore can be realized in devices with a limited amount of memory and/or limited processor capacity.
Another object is to make possible effective and correct decoding of a position code that codes a very large number of positions.
These objects are achieved completely or partially by a method for position coding according to claim 1, a computer program according to claim 19, a method in a coding device according to claim 20, a computer program according to claim 32, a method for decoding a position code according to claim 33, a computer program according to claim 41, a product according to claim 42 and devices according to claims 43-45.
A first aspect of the invention thus relates to a method for position coding, comprising coding positions in a first dimension on a surface in accordance with a primary number sequence, which has the property that the place in the primary number sequence of each partial sequence of a first predetermined length is unambiguously determined, each position in the first dimension being coded by any one of the partial sequences, the primary number sequence being built up of at least two secondary number sequences that have a smaller base than the base of the primary number sequence and that are used for determination of the partial sequences of the primary number sequence corresponding to the positions in the first dimension.
As the primary number sequence is built up of secondary number sequences with a smaller base, preferably at most the base 5, the table that is required to convert places in the primary number sequence into partial sequences of this can be replaced by several smaller tables that together require less memory. Thus it becomes in practice feasible to code coordinates for a very large number of positions.
The use of a primary number sequence for coding positions in at least a first dimension also makes it possible to achieve a position code with very good error-detection and error-correction properties. More specifically, each number in the primary number sequence is coded using partial sequences of a cyclic main number sequence. If partial sequences of the main number sequence are now recorded that are longer than what is required for position determination, error detection and error correction can be achieved by the main number sequence being designed in such a way that the longer partial sequences do not occur in certain incorrect versions, for example with one incorrect figure.
Also for the decoding, the fact is used that the primary number sequence is built up of secondary number sequences with smaller bases, the decoding being able to be carried out using several smaller tables and using the Chinese remainder theorem. The decoding can thereby be realized in, for example, a hand-held device with limited memory and processor capacity.
The position coding can be utilized for coding positions in both one and two dimensions. The coding in the second dimension can be carried out using the same principles and with different number sequences to those utilized for the coding in the first dimension or with the same number sequences.